package com.cuz.daileetcode.bat100;

import java.util.Arrays;

/**
 * 存在m个大楼
 * arr【】表示每一个电池的电量
 * 比如arr【】=【4，5，6】
 * 表示arr【0】可以让一个大楼撑住4分钟有电
 * 问这么多电池最多让m个大楼撑多久
 */
public class 电池分配大楼时间问题 {

    public static void main(String[] args) {
        int[] ints = {1, 2, 2, 4, 5};
        System.out.println(solution1(ints, 3));
    }

    public static int solution1(int[] arr, int m) {
        if (arr == null || arr.length == 0 || m > arr.length) {
            return -1;
        }
        int[] preSum = sortAndPreSum(arr);
        int ans = preSum[arr.length - 1] + 1;
        int mostLessAns = -1;
        while (mostLessAns + 1 != ans) {
            int mid = mostLessAns + ((ans - mostLessAns) >> 1);
            if (canKeepLive(arr, preSum, m, mid)) {
                mostLessAns = mid;
            } else {
                ans = mid;
            }
        }
        return mostLessAns;
    }

    private static int[] sortAndPreSum(int[] arr) {
        Arrays.sort(arr);
        int[] preSum = new int[arr.length];
        preSum[0] = arr[0];
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + arr[i];
        }
        return preSum;
    }

    private static boolean canKeepLive(int[] arr, int[] preSum, int m, int time) {
        // 1,2,2,3,4,5 time=3 firstGE=3 arr.len-firstGE=6-3 >=m表示3个电池无需要调换可以直接满足大楼
        int firstGE = findFirstBetterEqualThan(arr, time);
        if (firstGE != -1 && arr.length - firstGE >= m) {
            return true;
        }
        if (firstGE != -1) {
            m -= arr.length - firstGE;
        }
        //剩下的碎片电池能否满足大楼的供电
        return preSum[firstGE == -1 ? arr.length - 1 : firstGE - 1] >= m * time;
    }

    private static int findFirstBetterEqualThan(int[] arr, int target) {
        int left = -1;
        int right = arr.length;
        while (left + 1 != right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (right >= arr.length) {
            return -1;
        }
        return arr[right] >= target ? right : -1;
    }
}
